

import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;


/**
 *
 * @author Eric Beaudry
 */
public class GenPolitique3 {
	
	public static class MovementAndChance{
		int movement;
		double chance;
		
		public MovementAndChance(int m, double c){
			movement = m;
			chance = c;
		}
	}
	
	public static final long TEMPS_LIMITE = 9950; //950 millisecondes, donc un peu moins d'une seconde
	public static final long TEMPS_LIMITE_BASE = 8000;
	private static final Double FACTEUR_BONIFICATION = 40d;
	private static final Double DISCOUNT_FACTOR = 0.99;
    public static List<MovementAndChance> PossibilityOf1Move; 
    public static List<MovementAndChance> PossibilityOf1Dice; 
    public static List<MovementAndChance> PossibilityOf2Dice; 
    public static long tempsDepart;
    public static boolean DEBUG_MODE = false;
	public static boolean DEBUG_VALUE_MODE = false;

    static PolitiqueAvancee generate(Plateau plateau) {
    	tempsDepart = System.currentTimeMillis();
    	PolitiqueAvancee pol = new PolitiqueAvancee(plateau.nbCases);
    	//PolitiqueAvancee base = GenPolitique2.generate(plateau, TEMPS_LIMITE_BASE);
    	PolitiqueSimple polEnnemi = genPolitiqueNaive(plateau.nbCases);
    	
    	int[][] R = new int[plateau.nbCases][plateau.nbCases];
    	double[][] V = new double[plateau.nbCases][plateau.nbCases];
        
    	initiateValue(plateau,R,V);
        initiatePossibilities();
        
        int iter = 0;
    	while(resteTemps()){
    		iter++;
    		/*V = */completeAnIteration(plateau,R,V,pol, polEnnemi);
    		debugMode(plateau, R, V);
    	}
    	
    	if (DEBUG_MODE)
    		System.out.println("We did " + iter  + " iteration");
        
        return pol;
    }
    
	// On utilise Politique 2 pour tout les coup ou l'on est derri�re lui ou en avance de x (ou x pas grand)
	// Sinon on avance vraiment pas beaucoup (1 ou D) selon l'avance et le reste du parcours

	// Autre tactic, on se target quelque coup d'avance sur le joueur sauf, si l'on peut gagner ...
    	
    public static void completeAnIteration(Plateau p, int R[][], double V[][], PolitiqueAvancee polNous, PolitiqueSimple polEnnenmie){
       	
        int iter = 0;
    	while(iter < p.nbCases){
    		for(int pos1 = p.nbCases - 1 - iter; pos1 >= 0; pos1--){
    			computeValueAndAction(p, R, V, polNous, polEnnenmie, p.nbCases - 1 - iter, pos1);
    		}
    		for(int pos2 = p.nbCases - 2 - iter; pos2 >= 0; pos2--){
    			computeValueAndAction(p, R, V, polNous, polEnnenmie, pos2, p.getNbCases() - 1 - iter);
    		}
    		iter++;
    	}
    	
    	
    	/*
    	
    	System.out.println("*******************************\n R values : ");
    	for(int pos1 = 0 ; pos1 < p.getNbCases() - 1; pos1 ++){
    		for(int pos2 = 0 ; pos2 < p.getNbCases() - 1; pos2 ++){
    				System.out.print(R[pos1][pos2] + " ");
        	}
    		System.out.println("\n");
    	}
    	System.out.println("*******************************");
    	
    	
    	*/
    	
    }
    
    private static void computeValueAndAction(Plateau p, int[][] R,
			  double[][] V, PolitiqueAvancee polNous,
			  PolitiqueSimple polEnnenmie, int pos2, int pos1) {
    	double valueAndLostProb1move[] = new double[2];
    	double valueAndLostProb1dice[] = new double[2];
    	double valueAndLostProb2dice[] = new double[2];
    	valueAndLostProb1move[0] = Double.NEGATIVE_INFINITY;
    	valueAndLostProb1move[1] = 0;
    	valueAndLostProb1dice[0] = Double.NEGATIVE_INFINITY;
    	valueAndLostProb1dice[1] = 0;
    	valueAndLostProb2dice[0] = Double.NEGATIVE_INFINITY;
    	valueAndLostProb2dice[1] = 0;

    	//Dans le cas de mouvement de 1
    	valueAndLostProb1move[0] = 0;
    	for(MovementAndChance mouvementNous : PossibilityOf1Move){
    		computeValue(p, V, polEnnenmie, pos1, pos2, mouvementNous, valueAndLostProb1move);
    	}
    	valueAndLostProb1move[0] *= DISCOUNT_FACTOR;
    	valueAndLostProb1move[0] += R[pos1][pos2];

    	//Dans le cas de mouvement de 1 d�
    	if(p.getNextCase(pos1, 1) !=  (p.getNbCases() - 1) && Math.abs(pos1 - pos2) < p.getNbCases()/2)
    	{
    		valueAndLostProb1dice[0] = 0;
    		for(MovementAndChance mouvementNous : PossibilityOf1Dice){
    			computeValue(p, V, polEnnenmie, pos1, pos2, mouvementNous,valueAndLostProb1dice);
    		}
    		valueAndLostProb1dice[0] *= DISCOUNT_FACTOR;
    		valueAndLostProb1dice[0] += R[pos1][pos2];
    	}

    	//Dans le cas de mouvement de 2 dés
    	if( pos1 <= p.getNbCases() - 4 && p.getNextCase(pos1, 1) !=  (p.getNbCases() - 1)  && Math.abs(pos1 - pos2) < p.getNbCases()/2){
    		valueAndLostProb2dice[0] = 0;
    		for(MovementAndChance mouvementNous : PossibilityOf2Dice){
    			computeValue(p, V, polEnnenmie, pos1, pos2, mouvementNous, valueAndLostProb2dice);
    		}
    		valueAndLostProb2dice[0] *= DISCOUNT_FACTOR;
    		valueAndLostProb2dice[0] += R[pos1][pos2];
    	}

    	if(DEBUG_MODE && DEBUG_VALUE_MODE){
    		System.out.println("******************************\n Position : " + pos1 + " " + pos2);
    		System.out.println("Move of 1 : value : " + valueAndLostProb1move[0] + " lost prob : " + valueAndLostProb1move[1]);
    		System.out.println("Move of 1 dice : value : " + valueAndLostProb1dice[0] + " lost prob : " + valueAndLostProb1dice[1]);
    		System.out.println("Move of 2 dice : value : " + valueAndLostProb2dice[0] + " lost prob : " + valueAndLostProb2dice[1]);
    	}

    	if((valueAndLostProb1move[1] == 0 && valueAndLostProb2dice[1] == 0 && valueAndLostProb1dice[1] == 0) || (p.nbCases - 1 -pos1) <= (pos1 - pos2) ){
    		double bestValue = 0;
    		ActionType bestAction = null;

    		if(valueAndLostProb1move[0] > valueAndLostProb1dice[0]){
    			if(valueAndLostProb1move[0] > valueAndLostProb2dice[0]){
    				bestValue = valueAndLostProb1move[0];
    				bestAction = ActionType.UneSeuleCase;
    			}
    			else{
    				bestValue = valueAndLostProb2dice[0];
    				bestAction = ActionType.DeuxDes;
    			}
    		}
    		else
    		{
    			if(valueAndLostProb1dice[0] > valueAndLostProb2dice[0]){
    				bestValue = valueAndLostProb1dice[0];
    				bestAction = ActionType.UnDe;
    			}
    			else{
    				bestValue = valueAndLostProb2dice[0];
    				bestAction = ActionType.DeuxDes;
    			}
    		}	

    		V[pos1][pos2] = bestValue;
    		polNous.actions[pos1][pos2] = bestAction;
    		if(DEBUG_MODE && DEBUG_VALUE_MODE)
    			System.out.println("Chosen : " + bestAction.getLabel());
    	}
    	else{

    		double bestValueThroughtLostProb = 0;
    		ActionType bestAction = null;

    		if(valueAndLostProb1move[1] > valueAndLostProb1dice[1]){
    			if(valueAndLostProb1move[1] > valueAndLostProb2dice[1]){
    				bestValueThroughtLostProb = valueAndLostProb1move[0];
    				bestAction = ActionType.UneSeuleCase;
    			}
    			else{
    				bestValueThroughtLostProb = valueAndLostProb2dice[0];
    				bestAction = ActionType.DeuxDes;
    			}
    		}
    		else
    		{
    			if(valueAndLostProb1dice[1] > valueAndLostProb2dice[1]){
    				bestValueThroughtLostProb = valueAndLostProb1dice[0];
    				bestAction = ActionType.UnDe;
    			}
    			else{
    				bestValueThroughtLostProb = valueAndLostProb2dice[0];
    				bestAction = ActionType.DeuxDes;
    			}
    		}	

    		V[pos1][pos2] = bestValueThroughtLostProb;
    		polNous.actions[pos1][pos2] = bestAction;
    		if(DEBUG_MODE && DEBUG_VALUE_MODE)
    			System.out.println("Chosen : " + bestAction.getLabel());
    	}

    	if(DEBUG_MODE && DEBUG_VALUE_MODE)
    		System.out.println("********************************");
    }

    private static void computeValue(Plateau p, double[][] V,
    		PolitiqueSimple polEnnenmie, int pos1, int pos2,
    		MovementAndChance mouvementNous,
    		double valueAndLostProb[]) {
    	if(pos1 == p.getNbCases() -1 || pos2 == p.getNbCases() - 1){
    		valueAndLostProb[0] += V[pos1][pos2];
    		valueAndLostProb[1] = 0;
    	}
    	//Si l'autre avance de 1
    	else if(polEnnenmie.actions[pos2] == ActionType.UneSeuleCase){
    		for(MovementAndChance mouvementEnnemy : PossibilityOf1Move){
    			valueForMoves(p, V, pos1, pos2, mouvementNous, valueAndLostProb, mouvementEnnemy);
    		}
    	}
    	//Si l'autre avance d'un d�
    	else if (polEnnenmie.actions[pos2] == ActionType.UnDe){
    		for(MovementAndChance mouvementEnnemy : PossibilityOf1Dice){
    			valueForMoves(p, V, pos1, pos2, mouvementNous, valueAndLostProb, mouvementEnnemy);
    		}
    	}
    	else{
    		for(MovementAndChance mouvementEnnemy : PossibilityOf2Dice){
    			valueForMoves(p, V, pos1, pos2, mouvementNous, valueAndLostProb, mouvementEnnemy);
    		}
    	}

    }

    private static void valueForMoves(Plateau p, double[][] V, int pos1,
    		int pos2, MovementAndChance mouvementNous,
    		double[] valueAndLostProb, MovementAndChance mouvementEnnemy) {
    	valueAndLostProb[0] += mouvementNous.chance * mouvementEnnemy.chance * V[p.getNextCase(pos1, mouvementNous.movement)][p.getNextCase(pos2, mouvementEnnemy.movement)];

    	if(p.getNextCase(pos1, mouvementNous.movement) == p.nbCases-1 && pos1 != p.getNbCases()-1 && p.getNextCase(pos2, mouvementEnnemy.movement) == p.nbCases-1 && pos2 != p.getNbCases() - 1){
    		valueAndLostProb[1] += mouvementNous.chance * mouvementEnnemy.chance *FACTEUR_BONIFICATION ;
    	}
    }

    public static void initiateValue(Plateau p, int[][] R, double[][] V){
    	int longueur = p.getNbCases()-1;
    	double avancement = longueur/4;
    	for(int pos2 = 0; pos2 <= longueur; pos2++){
    		for(int pos1 = 0; pos1 <= longueur; pos1++){
        		V[pos1][pos2] = -( Math.pow((pos1-pos2-avancement), 2));
        		R[pos1][pos2] = (int) -(Math.pow((pos1-pos2-avancement), 2));
        	}
    	}   
    	
    	for(int pos2 = p.nbCases/2; pos2 < p.nbCases - 1; pos2++){
    		V[p.nbCases-1][pos2] = p.getNbCases();
    		R[p.nbCases-1][pos2] = p.getNbCases();
    	}
    }
    
    public static void initiatePossibilities(){
    	PossibilityOf1Dice = new ArrayList<MovementAndChance>();
    	PossibilityOf1Move = new ArrayList<MovementAndChance>();
    	PossibilityOf2Dice = new ArrayList<MovementAndChance>();
    	
    	//Action 1 : 1
    	PossibilityOf1Move.add(new MovementAndChance(1, 1.0));
    	//Action 2 : 1 d�
    	for(int i = 1; i <= 6; i++){
    		PossibilityOf1Dice.add(new MovementAndChance(i, 1.0/6.0));
    	}
    	//Action 3 : 2 d�s
    	PossibilityOf2Dice.add(new MovementAndChance(2, 1.0/36.0));
    	PossibilityOf2Dice.add(new MovementAndChance(3, 2.0/36.0));
    	PossibilityOf2Dice.add(new MovementAndChance(4, 3.0/36.0));
    	PossibilityOf2Dice.add(new MovementAndChance(5, 4.0/36.0));
    	PossibilityOf2Dice.add(new MovementAndChance(6, 5.0/36.0));
    	PossibilityOf2Dice.add(new MovementAndChance(7, 6.0/36.0));
    	PossibilityOf2Dice.add(new MovementAndChance(8, 5.0/36.0));
    	PossibilityOf2Dice.add(new MovementAndChance(9, 4.0/36.0));
    	PossibilityOf2Dice.add(new MovementAndChance(10, 3.0/36.0));
    	PossibilityOf2Dice.add(new MovementAndChance(11, 2.0/36.0));
    	PossibilityOf2Dice.add(new MovementAndChance(12, 1.0/36.0));
    }
    
    public static PolitiqueSimple genPolitiqueNaive(int nombreCase){
    	PolitiqueSimple polNaive = new PolitiqueSimple(nombreCase);
    	
    	for(int i = 0 ; i < 2 && i < nombreCase; i++)
    		polNaive.actions[nombreCase - i - 1] = ActionType.UneSeuleCase;
    	
    	for(int i = 2 ; i < 6 && i < nombreCase; i++)
    		polNaive.actions[nombreCase - i - 1] = ActionType.UnDe;
    	
    	for(int i = 6 ; i < nombreCase; i++)
    		polNaive.actions[nombreCase - i - 1] = ActionType.DeuxDes;
    	
    	return polNaive;
    }
    
    private static void debugMode(Plateau plateau, int[][] R, double[][] V) {
		if(DEBUG_MODE){
			System.out.println("R value for all data :");
			for(int l = 0; l < plateau.nbCases; l ++){
				for( int c = 0; c < plateau.nbCases; c++){
					System.out.print(R[l][c] + " ");
				}
				System.out.println();
			}
			
			System.out.println("V value for all data :");
			for(int l = 0; l < plateau.nbCases; l ++){
				for( int c = 0; c < plateau.nbCases; c++){
					System.out.print(V[l][c] + " ");
				}
				System.out.println();
			}
		}
	}

	private static boolean resteTemps() {
		return System.currentTimeMillis() - tempsDepart < TEMPS_LIMITE;
	}
     
    public static void main(String args[]) throws Exception {
        Plateau plateau = Plateau.load(new InputStreamReader(System.in));
        PolitiqueAvancee pol = generate(plateau);
        OutputStreamWriter out = new OutputStreamWriter(System.out);
        PolitiqueAvancee.save(pol, out);
        out.close();
    }

}
